class Solution(object):
    def subarraySum(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        total = 0
        nums_len = len(nums)
        for i in range(nums_len):
            count = 0
            for j in range(i, nums_len):
                count += nums[j]
                if count == k:
                    total += 1
        return total
    
    def subarraySumOptimized(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        total = 0
        nums_len = len(nums)
        m = {}
        m[0] = 1
        count = 0
        for i in range(nums_len):
            count += nums[i]
            v = count - k
            if v in m:
                total += m[v]
            if count not in m:
                m[count] = 0
            m[count] += 1      
        return total

s = Solution()
nums = [1,1,1]
k = 2
result = s.subarraySumOptimized(nums, k)
print(result)

nums = [1,2,3]
k = 3
result = s.subarraySumOptimized(nums, k)
print(result)
